Trellis encoding is a way of encoding data using a convolutional code prior to modulation such that the original data can be recovered at the receiver, even in the presence of a certain amount of noise on the received signal.
In national and international standards for DSL (digital subscriber line) technologies such as ADSL (e.g., ITU-T Recommendation G992.1 entitled “Asymmetrical digital subscriber line (ADSL) transceivers,” ITU-T Recommendation G992.3 entitled “Asymmetric digital subscriber line transceivers-2 (ADSL2),” and ITU-T Recommendation G992.4 entitled “Splitterless asymmetric digital subscriber line transceivers 2 (splitterless ADSL2)” which are all incorporated by reference herein in their entireties) a particular form of trellis encoding is used for mapping a set of input data bits U={u1, u2, . . . , uz} and input state bits S={s0, s1, s2, s3} onto two sets of output data bits V={v0, v1, . . . , vx−1}, W={w0, w1, . . . , wy−1} and output state bits S′={s′0, s′1, s′2, s′3}. V and W are subsequently encoded using QAM (quadrature amplitude modulation) onto a pair of tones in a DMT (discrete multi-tone) scheme, the two tones being encoded with respectively x-bit and y-bit QAM constellations. (Note that x+y=z+1; in other words, one more bit is produced in the V and W output data bits than were taken in as input data bits U). The process is then repeated with S′ forming the input state for the trellis encoding of the next set of input data bits U′ for the next tone-pair, yielding output data bits V′ and W′, and output state bits S″, and so on.
According to the applicable standards, the equations governing the output are as follows:v0=u3 v1=u1u3 vn=un+2, for n=2 to (x−1)w0=u2u3 w1=s0u1u2u3 wn=un+x, for n=2 to (y−1)s′0=s1s3u1 s′1=s2u2 s′2=s0 s′3=s1 
The symbol  represents the logical exclusive-OR operation.
An alternative naming scheme used hereafter is for input U to be identified as U(0), U′ as U(1), etc., output V to be identified as V(1), V′ as V(2), etc., output W to be identified as W(1), W′ as W(2), etc., input S to be identified as S(0), output or input S′ to be identified as S(1), output or input S″ to be identified as S(2) etc.
In older designs for transmission systems using trellis encoding (such as DSL modems), which are in general more hardware oriented, the trellis encoding of data, for subsequent modulation of tones for transmission, is typically performed by fixed-function logic circuits. However, such system designs are commonly hard to adapt for varying application requirements. In order to increase flexibility in modem development and application, it has become more common to use software to perform the various functions in a DMT-based transmitting device. As the various performance levels (such as data-rates) required of such devices increase, the pressure on the software to perform efficiently the individual processing tasks (such as trellis encoding), which make up the overall transmitter function, likewise increases.
One reason is that performing the trellis encoding operation purely in software is typically quite complex to implement. Using conventional instructions (e.g. bit-wise shift, bit-wise and, bit-wise exclusive-OR, etc.) may take many cycles, or even tens of cycles, to perform trellis encoding for a single tone-pair. In some circumstances there may be hundreds or even thousands of tones for which the associated data bits must be encoded, per transmitted symbol, and several thousand symbols per second may need to be transmitted.
The trellis encoding process can therefore represent a significant proportion of the total computational cost for a software-based DMT transmitter, especially in the case of a system where one processor handles the operations for multiple independent transmission channels (e.g., in a multi-line DSL modem in the central office). With increasing workloads (in respect of the average number of tones used in each transmission channel), it becomes necessary to improve the efficiency of trellis encoding of data in such software-based DMT transmitters.
Therefore, what is needed is a system and method that significantly reduce a number of cycles needed for software to perform trellis encoding of data in accordance with a mapping scheme specified in international standards.